package com.shm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: shm
 * @dateTime: 2020/9/19 18:08
 * @description: 404. 左叶子之和
 * 计算给定二叉树的所有左叶子之和。
 *
 * 示例：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 */
public class SumOfLeftLeaves {
    int sum = 0;

    public int sumOfLeftLeaves(TreeNode root) {
        dfs(root);
        return sum;
    }

    public void dfs(TreeNode root){
        if (root==null){
            return;
        }
        if (root.left!=null&&root.left.left==null&&root.left.right==null){
            sum+=root.left.val;
        }else {
            dfs(root.left);
        }
        dfs(root.right);
    }


    /**
     * @author: shm
     * @dateTime: 2020/9/19 19:38
     * @description: 方法二：广度优先搜索
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是树中的节点个数。
     *
     * 空间复杂度：O(n)O(n)。空间复杂度与广度优先搜索使用的队列需要的容量相关，为 O(n)O(n)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/sum-of-left-leaves/solution/zuo-xie-zi-zhi-he-by-leetcode-solution/
     */
    public int sumOfLeftLeaves_2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                if (isLeafNode(node.left)) {
                    ans += node.left.val;
                } else {
                    queue.offer(node.left);
                }
            }
            if (node.right != null) {
                if (!isLeafNode(node.right)) {
                    queue.offer(node.right);
                }
            }
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }
}
